package algorithm.dynamicProgramming.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

//53. 最大子序和
public class MaxSubArray {
    public static void main(String[] args) {
//        int[] data = {-1,-2};
        int[] data = {-2};
//        int[] data = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray2(data));
    }

    //超出内存限制
    public static int maxSubArray(int[] nums) {
        if (nums.length==1){
            return nums[0];
        }

        ArrayList<Integer> list = new ArrayList<>();
        int sum = 0;
        int res = Integer.MIN_VALUE;
        for (int i=0;i<nums.length-1;i++){
             sum=nums[i];
            int p=i;
            int q=i+1;
            while (true){
               sum+=nums[q];
               list.add(sum);
                q++;
                if (q==nums.length){
                    break;
                }
            }
        }
        for (int i =0;i<nums.length;i++){
            list.add(nums[i]);
        }
        for (int x :list){
            res = Math.max(x,res);
        }
        return res;
    }

    //动态规划
    public static int maxSubArray2(int[] nums) {
        int res = nums[0];
        int n = nums.length;
        int[] f = new int[n];
        f[0]=nums[0];
        for (int i =1;i<nums.length;i++){
            f[i] = Math.max(f[i-1]+nums[i],nums[i]);
            res = Math.max(res,f[i]);
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(f));
       return res;

    }

    //贪心
    public static int maxSubArray3(int[] nums) {
        int res = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            res = Math.max(sum,res);
            if (sum<0){
                sum=0;
            }
        }
        return res;
    }

    //暴力
    public static int maxSubArray4(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i =0;i<nums.length;i++){
            int sum = 0;
            for (int j = i;j<nums.length;j++){
                sum+=nums[j];
                if (sum>max){
                    max = sum;
                }
            }
        }
        return max;
    }
}
